# class Solution:
#     def minSteps(self, n: int) -> int:
#         if n == 1:
#             return 0
#         dp = [float('inf')] * (n+1)
#         dp[1] = 0
#         for i in range(2, n+1):
#             dp[i] = i
            
#             for j in range(2, int(i**2)+1):
#                 if i % j == 0:
#                     dp[i] = min(dp[i], dp[j]+i//j)
#                     dp[i] = min(dp[i], dp[i//j]+j)
#         return dp[n]
# if __name__ == '__main__':
#     s = Solution()
#     print(s.minSteps(3))

# 动态规划法：
# 定义：
# dp[i] = 得到恰好 i 个 'A' 需要的最少操作次数
# 状态转移原理
# 基本情况
# dp[1] = 0：一开始就有1个'A'，不需要任何操作
# 关键洞察
# 要得到 i 个 'A'，我们有两种方式：
# 方式1：从1个'A'开始，逐个粘贴
# 复制1次 + 粘贴(i-1)次 = i 次操作
# 这是最坏情况，适用于质数
# 方式2：通过因子分解优化
# 如果 i 可以被 j 整除（即 i % j == 0）
# 那么我们可以先得到 j 个'A'（需要 dp[j] 次操作）
# 然后复制这 j 个'A'（1次操作）
# 再粘贴 (i/j - 1) 次得到 i 个'A'
# 总操作次数 = dp[j] + 1 + (i/j - 1) = dp[j] + i/j
# 状态转移方程
# dp[i] = min(i, min{ dp[j] + i/j 对于所有 j 是 i 的因子 })


class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0
        result = 0
        factor = 2
        while n > 1:
            while n%factor ==0:
                result += factor # 累加质因数
                n //= factor # 整除质因数
            factor += 1
        return result
if __name__ == '__main__':
    s = Solution()
    print(s.minSteps(3))

# 质因数法：
# 算法步骤：
# 从最小的质数 2 开始

# 不断除以当前质数，直到不能整除为止

# 累加所有质因数

# 移动到下一个质数，重复过程
        